public class test_2_4 {

//    1.反转链表:
//    示例 1：
//    输入：head = [1,2,3,4,5]
//    输出：[5,4,3,2,1]
//
//    示例 2：
//    输入：head = [1,2]
//    输出：[2,1]
//
//    示例 3：
//    输入：head = []
//    输出：[]

    public ListNode reverseList(ListNode head) {
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode cur=head.next;
        head.next=null;
        while (cur!=null){
            ListNode curnext=cur.next;
            cur.next=head;
            head=cur;
            cur=curnext;
        }
        return head;
    }



//     2.链表的中间结点
//     给定一个头结点为 head 的非空单链表，返回链表的中间结点。
//     如果有两个中间结点，则返回第二个中间结点。
//     示例 1：
//     输入：[1,2,3,4,5]
//     输出：此列表中的结点 3 (序列化形式：[3,4,5])
//     返回的结点值为 3 。
//     示例 2：
//     输入：[1,2,3,4,5,6]
//     输出：此列表中的结点 4 (序列化形式：[4,5,6])
//     由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

    public ListNode middleNode(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }



//    3.链表中倒数第k个结点
//    描述:
//    输入一个链表，输出该链表中倒数第k个结点。
//    示例1
//    输入：1,{1,2,3,4,5}
//    返回值：{5}

    public ListNode FindKthToTail(ListNode head,int k) {
        if(k<=0||head==null){
            return null;
        }
        ListNode fast=head;
        ListNode slow=head;
        while (k-1!=0){
            fast=fast.next;
            if(fast==null){
                return null;
            }
            k--;
        }
        while (fast!=null&&fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }



//    4.合并两个有序链表
//    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//    示例 1：
//    输入：l1 = [1,2,4], l2 = [1,3,4]
//    输出：[1,1,2,3,4,4]
//    示例 2：
//    输入：l1 = [], l2 = []
//    输出：[]
//    示例 3：
//    输入：l1 = [], l2 = [0]
//    输出：[0]

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode node=new ListNode();
        ListNode tmp=node;
        while (list1!=null&&list2!=null){
            if(list1.val<list2.val){
                tmp.next=list1;
                list1=list1.next;
            }else{
                tmp.next=list2;
                list2=list2.next;
            }
            tmp=tmp.next;
        }
        if(list1!=null){
            tmp.next=list1;
        }
        if(list2!=null){
            tmp.next=list2;
        }
        return node.next;
    }



//    5.链表的回文结构
//    链表,栈
//    描述
//    对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。
//    给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
//    测试样例：1->2->2->1
//    返回：true

    public boolean chkPalindrome(ListNode A) {
        if(A==null){
            return false;
        }
        if(A.next==null){
            return true;
        }
        ListNode fast=A;
        ListNode slow=A;
        while (fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        ListNode cur=slow.next;
        while (cur!=null){
            ListNode curnext=cur.next;
            cur.next=slow;
            slow=cur;
            cur=curnext;
        }
        while (A!=slow){
            if(A.val!=slow.val){
                return false;
            }
            if(A.next==slow){
                return true;
            }
            A=A.next;
            slow=slow.next;
        }
        return true;
    }
}















